High performance computers and work stations are used extensively for three-dimensional graphics processing. In three-dimensional graphics processing, one or more three-dimensional images is displayed on a two-dimensional graphics display such as a high resolution graphics screen. Computer Aided Design (CAD) systems allow users to create a three-dimensional representations using lines, points and vectors. Three-dimensional image data may be used in the drafting and documentation phases of product design, and may also be used to control product manufacture.
Product designers, such as architects and engineers, still begin the design process on paper and communicate design concepts on paper. Although CAD has succeeded at automating drafting, documentation and manufacturing it has met with limited success at "visualization".
Visualization is the first step in creating a spatial design. Visualization allows a user to create, explore, change, interact with and share a complete simulation of a three-dimensional world. It would be highly desirable for a designer to use the computer to create, modify and observe a three-dimensional space.
Unfortunately, Computer-Aided Visualization (CAV) has not been heretofore used extensively because of two main problems. First, the creation and manipulation of objects in three-dimensional space on a computer typically requires high performance computers or workstations to produce real-time visualization. Second, efficient techniques have heretofore not been available for moving an observer through a three-dimensional space on a graphics display along all six degrees of freedom. Each of these problems will be described in detail.
The creation of a three-dimensional space on a two-dimensional display is often referred to as "rendering". It is difficult to perform rendering in real time using conventional graphics techniques. A major problem in real time rendering is determining spatial priority. That is, it is difficult to calculate which objects are in front of other objects from a particular point of view or reference position.
A number of techniques have been developed to determine spatial priority. Many of these techniques are described in a textbook entitled Computer Graphics, Principles and Practice, by Foley et al. (Second Edition, 1990) published by Addison-Wesley Publishing Company, Inc., the disclosure of which is hereby incorporated herein by reference. However, these techniques have been so resource intensive that real time rendering typically cannot be performed without the use of expensive supercomputers or workstations.
One technique which has been used to render a three-dimensional space is referred to as a "z-buffer". See the Foley et al. text, pages 668-672. In a z-buffer, a separate buffer is provided which includes a depth field for each pixel on the two-dimensional display. When a three-dimensional space is rendered on the display, a new value in the z-buffer is calculated for every pixel. The newly calculated depth is then displayed on a graphics display using well known techniques. Since repositioning of the three-dimensional data requires a recalculation of the depth value for each pixel, this technique is very resource intensive.
A second technique for recreating a three-dimensional space in a graphics computer system is referred to as "ray tracing" or "ray casting". See the Foley et al. textbook, pages 701-715. In this technique, the visibility of surfaces is determined by tracing imaginary rays of light from the viewer's eye to the objects in the scene. Since large numbers of rays must be traced in order to produce a high quality image of spatial priority, this technique also is typically not a real time technique unless high performance computers are used.
Binary space partitions have also been used for three-dimensional rendering. See the Foley et al. textbook, pages 701-715. Binary space partitioning breaks the three-dimensioned space into a plurality of smaller spaces and each smaller space is rendered individually. The rendered smaller spaces are then combined. Again, this technique is resource intensive.
Yet another technique for three-dimensional rendering is the "painters algorithm" also referred to as a "depth-sort" algorithm. See the Foley et al. text, pages 673-675. In the painters algorithm, the farthest objects are first rendered and then closer objects are rendered on top of the farther objects, with the closer objects masking the farther objects. Since this requires all of the objects in the three-dimensional space to be redrawn every time a viewing position is changed, the algorithm is time consuming.
A final technique used for three-dimensional rendering is "scan line" technique. See the Foley et al. text pages 885-887. The three-dimensional space is scanned pixel by pixel and rendered pixel by pixel. Since the rendering is performed individually for each pixel, this technique is highly resource intensive.
In summary, the rendering of a three-dimensional space from a particular point of view is extremely time consuming because spatial priority determination is resource intensive. Accordingly, real time rendering has been difficult to perform on conventional desktop or personal computers.
The second major problem in real time three-dimensional computer aided visualization is allowing an observer or reference point to easily move in the three-dimensional computer-generated scene along all six degrees of freedom. As is well known to those having skill in the art, an observer of a real three-dimensional space can move in six degrees of freedom by walking through the space and turning his head. The six degrees of freedom are translation along three orthogonal axis (often referred to as x, y and z axis) and rotation about the three orthogonal axis (often referred to as roll, pitch, and yaw).
Unfortunately, typical computer input devices which control movement through computer generated three-dimensional scenes have been either a keyboard or a joystick. The keyboard is an unnatural movement input device because it requires multiple keystrokes to move forward, or it assumes a velocity set by numeric keys and uses other keys to change directions. Joysticks are an improvement over the keyboard but are useful primarily for airplane simulators where user control about six degrees of freedom is not required. The joystick typically assumes a forward velocity, and the viewer uses the joystick to modify direction. There have also been a number of mouse based control systems used with computer based flight simulators, but these have typically been based upon the control system used by the joystick.
One attempt to improve the freedom of movement in a graphics display of a three-dimensional space has been implemented in a computer adventure game entitled "The Colony" which is described in a manual entitled "The Colony" published in 1988 by Mindscape, Inc. In this computer game, a cartesian grid was overlaid on top of the computer generated image, where the center of the grid is the center of the image. When the mouse is at this exact center, no motion occurs. As the mouse is moved up along the vertical axis from the center, the observer's position begins to move forward through the three-dimensional space. The distance from the center determines the speed of forward movement. Return the mouse to the center causes all motion to cease. If the user moves the mouse vertically downward from the center, the observer's position begins to move backwards. Again, the distance from the center determines velocity. The user can turn by moving the mouse along the horizontal axis. Movement to the left makes the observer turn left. The angular velocity of the turn is determined by the distance from the center. Movement to the right makes the observer turn to the right, with the angular velocity being determined by the distance from the center.
The above described movement input technique allows the reference position or observer to stop and walk backward. However, this technique does not allow the observer to efficiently move along all six degrees of freedom. In particular, it does not allow the user to easily move directly to the left or right, to change altitude, to change pitch or to change roll.
In summary, there is a great need in three-dimensional graphics processing, for real time three-dimensional rendering which allows a user to move through the three-dimensional space in real time along all six degrees of freedom, and which can be implemented using low cost personal computers.